class TreeNode {
  /**
   * @description: 定义二叉树节点
   * @param {Number} val
   * @param {TreeNode} left
   * @param {TreeNode} right
   */
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
/**
 * @description: 定义二叉树
 * @param {TreeNode} TreeNode
 * @param {Number} val
 * @return {TreeNode}
 */
function createTree(TreeNode, val) {
  if (val > 7) {
    return null;
  }
  const node = new TreeNode(val);
  node.left = createTree(TreeNode, val * 2);
  node.right = createTree(TreeNode, val * 2 + 1);

  return node;
}

/**
 * @description:
 * @param {TreeNode} root
 * @return {Array} morris节点访问顺序
 */
function morris(root) {
  let current = root;
  let mostRight = null;
  const result = [];

  while (current !== null) {
    result.push(current.val);
    mostRight = current.left;

    if (mostRight !== null) {
      // 获取当前节点左子树的最右节点
      while (mostRight.right !== null && mostRight.right !== current) {
        mostRight = mostRight.right;
      }
      // 当前节点首次访问
      if (mostRight.right === null) {
        mostRight.right = current;
        current = current.left;
        continue;
      } else {
        // 当前节点第二次访问
        mostRight.right = null;
      }
    } else {
      // 当前节点没有左节点的情况
    }
    current = current.right;
  }
  return result;
}
/**
 * @description: 二叉树preorder
 * @param {TreeNode} root
 * @return {Array}
 */
function morrisPre(root) {
  let current = root;
  let mostRight = null;
  const result = [];

  while (current !== null) {
    mostRight = current.left;

    if (mostRight !== null) {
      while (mostRight.right !== null && mostRight.right !== current) {
        mostRight = mostRight.right;
      }

      if (mostRight.right === null) {
        result.push(current.val);
        mostRight.right = current;
        current = current.left;
        continue;
      } else {
        mostRight.right = null;
      }
    } else {
      result.push(current.val);
    }

    current = current.right;
  }
  return result;
}
/**
 * @description: inorder
 * @param {TreeNode} root
 * @return {Array}
 */
function morrisIn(root) {
  let current = root;
  let mostRight = null;
  const result = [];

  while (current !== null) {
    mostRight = current.left;

    if (mostRight !== null) {
      while (mostRight.right !== null && mostRight.right !== current) {
        mostRight = mostRight.right;
      }

      if (mostRight.right === null) {
        mostRight.right = current;
        current = current.left;
        continue;
      } else {
        mostRight.right = null;
      }
    } else {
    }

    result.push(current.val);
    current = current.right;
  }
  return result;
}

/**
 * @description: postorder
 * @param {TreeNode} root
 * @return {Array}
 */
function morrisPost(root) {
  let current = root;
  let mostRight = null;
  const result = [];

  function setResult(root) {
    const node = reverseTree(root);
    let curr = node;
    while (curr) {
      result.push(curr.val);
      curr = curr.right;
    }
    reverseTree(node);
  }

  function reverseTree(root) {
    let preNode = null;
    let curr = root;

    while (curr) {
      let tempNode = curr.right;
      curr.right = preNode;
      preNode = curr;
      curr = tempNode;
    }

    return preNode;
  }

  while (current !== null) {
    mostRight = current.left;

    if (mostRight !== null) {
      while (mostRight.right !== null && mostRight.right !== current) {
        mostRight = mostRight.right;
      }

      if (mostRight.right === null) {
        mostRight.right = current;
        current = current.left;
        continue;
      } else {
        mostRight.right = null;
        setResult(current.left);
      }
    } else {
    }

    current = current.right;
  }
  setResult(root);
  return result;
}

/**
 * @description: 是否是搜索二叉树
 * @param {TreeNode} root
 * @return {Boolean}
 */
function morrisIsBST(root) {
  let current = root;
  let mostRight = null;
  let preVal = null;

  while (current !== null) {
    mostRight = current.left;

    if (mostRight !== null) {
      while (mostRight.right !== null && mostRight.right !== current) {
        mostRight = mostRight.right;
      }

      if (mostRight.right === null) {
        mostRight.right = current;
        current = current.left;
        continue;
      } else {
        mostRight.right = null;
      }
    } else {
    }
    if (preVal !== null && preVal >= current.val) {
      return false;
    }
    preVal = current.val;
    current = current.right;
  }
  return true;
}

// test
const root = createTree(TreeNode, 1);

console.log(morrisIsBST(root));
